<h2>题目编号 : 255</h2>
<div style="color:#666;font-size:80%;">11 September 2009</div><br />
<div class="problem_content">
<p>We define the <i>rounded-square-root</i> of a positive integer <var>n</var> as the square root of <var>n</var> rounded to the nearest integer.</p>

<p>The following procedure (essentially Heron&#39;s method adapted to integer arithmetic) finds the rounded-square-root of <var>n</var>:</p>
<p>Let <var>d</var> be the number of digits of the number <var>n</var>.<br />
If <var>d</var> is odd, set <var>x</var><img src="" style="display:none;" alt="_(" /><sub>0</sub><img src="" style="display:none;" alt=")" /> = 2<img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' />10<img src="" style="display:none;" alt="^(" /><sup>(<var>d</var>-1)&frasl;2</sup><img src="" style="display:none;" alt=")" />.<br />
If <var>d</var> is even, set <var>x</var><img src="" style="display:none;" alt="_(" /><sub>0</sub><img src="" style="display:none;" alt=")" /> = 7<img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' />10<img src="" style="display:none;" alt="^(" /><sup>(<var>d</var>-2)&frasl;2</sup><img src="" style="display:none;" alt=")" />.<br />
Repeat:</p>
<p align='center'>
<img src="project/images/p_255_Heron.gif" /></p>
<!--
<table align='center'>
<tr><td><var>x</var><img src="" style="display:none;" alt="_(" /><sub><var>k</var>+1</sub><img src="" style="display:none;" alt=")" /> =</td>
<td style='font-size:220%'>&#8970;</td>
<td style='text-align:center;'><var>x</var><img src="" style="display:none;" alt="_(" /><sub><var>k</var></sub><img src="" style="display:none;" alt=")" /> + <img src='images/symbol_lceil.gif' width='6' height='16' alt='&lceil;' border='0' style='vertical-align:middle;' /><var>n</var>&frasl;<var>x</var><img src="" style="display:none;" alt="_(" /><sub><var>k</var></sub><img src="" style="display:none;" alt=")" /><img src='images/symbol_rceil.gif' width='6' height='16' alt='&rceil;' border='0' style='vertical-align:middle;' /><br />
<img src='images/blackdot.gif' width='75' height='1' alt='' /><br />
2</td><td><td style='font-size:220%'>&#8971;</td></tr>
</table> -->

<p>until <var>x</var><img src="" style="display:none;" alt="_(" /><sub><var>k</var>+1</sub><img src="" style="display:none;" alt=")" /> = <var>x</var><img src="" style="display:none;" alt="_(" /><sub><var>k</var></sub><img src="" style="display:none;" alt=")" />.
</p>
<p>As an example, let us find the rounded-square-root of <var>n</var> = 4321.<br />
<var>n</var> has 4 digits, so <var>x</var><img src="" style="display:none;" alt="_(" /><sub>0</sub><img src="" style="display:none;" alt=")" /> = 7<img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' />10<img src="" style="display:none;" alt="^(" /><sup>(4-2)&frasl;2</sup><img src="" style="display:none;" alt=")" /> = 70.<br />
<img src='project/images/p_255_Example.gif'>
<!--<var>x</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /> = <img src='images/symbol_lfloor.gif' width='6' height='16' alt='&lfloor;' border='0' style='vertical-align:middle;' />(70 + <img src='images/symbol_lceil.gif' width='6' height='16' alt='&lceil;' border='0' style='vertical-align:middle;' />4321&frasl;70<img src='images/symbol_rceil.gif' width='6' height='16' alt='&rceil;' border='0' style='vertical-align:middle;' />)&frasl;2<img src='images/symbol_rfloor.gif' width='6' height='16' alt='&rfloor;' border='0' style='vertical-align:middle;' /> = 66.<br />
<var>x</var><img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" /> = <img src='images/symbol_lfloor.gif' width='6' height='16' alt='&lfloor;' border='0' style='vertical-align:middle;' />(66 + <img src='images/symbol_lceil.gif' width='6' height='16' alt='&lceil;' border='0' style='vertical-align:middle;' />4321&frasl;66<img src='images/symbol_rceil.gif' width='6' height='16' alt='&rceil;' border='0' style='vertical-align:middle;' />)&frasl;2<img src='images/symbol_rfloor.gif' width='6' height='16' alt='&rfloor;' border='0' style='vertical-align:middle;' /> = 66.--><br />
Since <var>x</var><img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" /> = <var>x</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" />, we stop here.<br />
So, after just two iterations, we have found that the rounded-square-root of 4321 is 66 (the actual square root is 65.7343137&hellip;).
</p>
<p>The number of iterations required when using this method is surprisingly low.<br />
For example, we can find the rounded-square-root of a 5-digit integer (10,000 <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <var>n</var> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 99,999) with an average of 3.2102888889 iterations (the average value was rounded to 10 decimal places).
</p>
<p>Using the procedure described above, what is the average number of iterations required to find the rounded-square-root of a 14-digit number (10<img src="" style="display:none;" alt="^(" /><sup>13</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <var>n</var> <img src='images/symbol_lt.gif' width='10' height='10' alt='&lt;' border='0' style='vertical-align:middle;' /> 10<img src="" style="display:none;" alt="^(" /><sup>14</sup><img src="" style="display:none;" alt=")" />)?<br />
Give your answer rounded to 10 decimal places.
</p>
<p>Note: The symbols <img src='images/symbol_lfloor.gif' width='6' height='16' alt='&lfloor;' border='0' style='vertical-align:middle;' /><var>x</var><img src='images/symbol_rfloor.gif' width='6' height='16' alt='&rfloor;' border='0' style='vertical-align:middle;' /> and <img src='images/symbol_lceil.gif' width='6' height='16' alt='&lceil;' border='0' style='vertical-align:middle;' /><var>x</var><img src='images/symbol_rceil.gif' width='6' height='16' alt='&rceil;' border='0' style='vertical-align:middle;' /> represent the <dfn title='the largest integer not greater than x'>floor function</dfn> and <dfn title='the smallest integer not less than x'>ceiling function</dfn> respectively.
</p>
</div><br />
